#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->VertexList = malloc(sizeof(datatype) * graph->MaxVertex);
	// graph->VertexList = calloc(Default_Vertex_Size, sizeof(datatype));
	if (graph->VertexList == NULL)
		return -1;
	graph->Edge = malloc(sizeof(int *) * graph->MaxVertex);
	if (graph->VertexList == NULL)
		return -2;
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		graph->Edge[i] = malloc(sizeof(int) * graph->MaxVertex);
		if (graph->Edge[i] == NULL)
			return -3;
	}
	for (int i = 0; i < graph->MaxVertex; i++)
	{
		for (int j = 0; j < graph->MaxVertex; j++)
		{
			graph->Edge[i][j] = 0;
		}
	}
	return 0;
}
void Show(Graph *graph)
{
	printf("  ");
	for (int i = 0; i < graph->NumVertex; i++)
		printf("%c ", graph->VertexList[i]);
	printf("\n");
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%c ", graph->VertexList[i]);
		for (int j = 0; j < graph->NumVertex; j++)
			printf("%d ", graph->Edge[i][j]);
		printf("\n");
	}
	printf("\n");
}
int InsertVertex(Graph *graph, datatype vertex)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->VertexList[graph->NumVertex++] = vertex;
	return 0;
}
int GetVertexPosition(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; i++)
	{
		if (graph->VertexList[i] == vertex)
			return i;
	}
	return -1;
}
int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2, int cost)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (p1 == p2)
		return -2;
	graph->Edge[p1][p2] = cost;
	// graph->Edge[p1][p2] = graph->Edge[p2][p1] = 1;
	++graph->NumEdge;
	return 0;
}
int RemoveVertex1(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	//顶点列表中的删除顶点后的顶点前移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		graph->VertexList[i] = graph->VertexList[i + 1];
	//统计删除顶点连接的边数
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//行上移
	for (int i = pos; i < graph->NumVertex - 1; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[i][j] = graph->Edge[i + 1][j];
	//列上移
	for (int i = pos; i < graph->NumVertex; ++i)
		for (int j = 0; j < graph->NumVertex; ++j)
			graph->Edge[j][i] = graph->Edge[j][i + 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}
int RemoveVertex2(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	int numedge = 0;
	for (int i = 0; i < graph->NumVertex; ++i)
		numedge += graph->Edge[pos][i];
	//修改顶点列表
	graph->VertexList[pos] = graph->VertexList[graph->NumVertex - 1];
	//行覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[pos][i] = graph->Edge[graph->NumVertex - 1][i];
	//列覆盖
	for (int i = 0; i < graph->NumVertex; i++)
		graph->Edge[i][pos] = graph->Edge[i][graph->NumVertex - 1];
	--graph->NumVertex;
	graph->NumEdge -= numedge;
	return 0;
}
int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	if (graph->Edge[p1][p2] == 0) //本来就没有边
		return -2;
	graph->Edge[p1][p2] = graph->Edge[p2][p1] = 0;
	--graph->NumEdge;
	return 0;
}
int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int pos = GetVertexPosition(graph, vertex);
	if (pos == -1)
		return -1;
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->Edge[pos][i] != 0)
			return i;
	}
	return -2;
}
int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosition(graph, vertex1);
	int p2 = GetVertexPosition(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	for (int i = p2 + 1; i < graph->NumVertex; i++)
	{
		if (graph->Edge[p1][i] != 0)
			return i;
	}
	return -1;
}

void DestoryGraph(Graph *graph)
{
	free(graph->VertexList);
	graph->VertexList = NULL;
	for (int i = 0; i < graph->MaxVertex; i++)
		free(graph->Edge[i]);
	free(graph->Edge);
	graph->Edge = NULL;
	graph->MaxVertex = graph->NumVertex = graph->NumEdge = 0;
}

void CriticalPath(Graph *graph)
{
	int n = graph->NumVertex;

	//初始化最早开始时间数组和最晚开始时间数组
	int *ve = malloc(sizeof(int) * n);
	int *vl = malloc(sizeof(int) * n);
	if (ve == NULL || vl == NULL)
		return;
	for (int i = 0; i < n; i++)
	{
		ve[i] = 0;
		vl[i] = MAX_COST; //最晚开始时间要初始化为最大值
	}

	//求解各结点的最早开始时间
	for (int i = 0; i < n - 1; i++)
	{
		int j = GetFirstNeighbor(graph, graph->VertexList[i]);
		while (j != -1)
		{
			int weight = GetWeight(graph, i, j);
			if (ve[i] + weight > ve[j])
				ve[j] = ve[i] + weight; //更新j结点的最早开始时间
			j = GetNextNeighbor(graph, graph->VertexList[i], graph->VertexList[j]);
		}
	}

	vl[0] = ve[0];  //起始点的最早开始时间和最晚开始时间都为0
	vl[n - 1] = ve[n - 1];  //终止点的最晚开始时间=最早开始时间

	//求解各结点的最晚开始时间(反着推,从倒数第二个结点开始,最后一个和第一个不用求)
	for (int i = n - 2; i > 0; i--)
	{
		int j = GetFirstNeighbor(graph, graph->VertexList[i]);
		while (j != -1)
		{
			int weight = GetWeight(graph, i, j);
			if (vl[j] - weight < vl[i])
				vl[i] = vl[j] - weight; //求解最小的最迟时间
			j = GetNextNeighbor(graph, graph->VertexList[i], graph->VertexList[j]);
		}
	}

	//打印Ae和Al数组(测试用)
	printf("Ae[]:");
	for (int i = 0; i < n; i++)
		printf("%d ", ve[i]);
	printf("\n");
	printf("Al[]:");
	for (int i = 0; i < n; i++)
		printf("%d ", vl[i]);
	printf("\n");

	//根据最早开始时间和最晚开始时间求解关键路径
	int Ae, Al;
	for (int i = 0; i < n; i++)
	{
		int j = GetFirstNeighbor(graph, graph->VertexList[i]);
		while (j != -1)
		{
			Ae = ve[i];  //这条边的最早开始时间
			Al = vl[j] - GetWeight(graph, i, j);  //这条边的最晚开始时间
			if (Ae == Al)
				printf("<%c-->%c>:%d\n", graph->VertexList[i], graph->VertexList[j], GetWeight(graph, i, j));
			j = GetNextNeighbor(graph, graph->VertexList[i], graph->VertexList[j]);
		}
	}

	#if 0   //我的写法
	for (int i = 0; i < n - 1; i++)
	{
		if (ve[i] == vl[i])
		{
			int j = GetFirstNeighbor(graph, graph->VertexList[i]);
			while (j != -1)
			{
				if (ve[j] == vl[j])
					printf("<%c-->%c>:%d\n", graph->VertexList[i], graph->VertexList[j], GetWeight(graph, i, j));
				j = GetNextNeighbor(graph, graph->VertexList[i], graph->VertexList[j]);
			}
		}
	}
	#endif

	free(ve);
	free(vl);
}

int GetWeight(Graph *graph, int v1, int v2)
{
	return graph->Edge[v1][v2];
}